//Code inspired by Glenn Fowler's sudoku solver/generator
//The original is published under the following license
		/***********************************************************************
		*               Original software is part of the ast package               *
		*          Copyright (c) 2005-2009 AT&T Intellectual Property          *
		*                      and is licensed under the                       *
		*                  Common Public License, Version 1.0                  *
		*                    by AT&T Intellectual Property                     *
		*                                                                      *
		*                A copy of the License is available at                 *
		*            http://www.opensource.org/licenses/cpl1.0.txt             *
		*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
		*                                                                      *
		*              Information and Software Systems Research               *
		*                            AT&T Research                             *
		*                           Florham Park NJ                            *
		*                                                                      *
		*                 Glenn Fowler <gsf@research.att.com>                  *
		***********************************************************************/
//This is a MODIFIED version of the original code 
#include "cantables.h"

byte	tswap[18][9][9] ={
	{
		{  0, 1, 2, 3, 4, 5, 6, 7, 8 },
		{  9,10,11,12,13,14,15,16,17 },
		{ 18,19,20,21,22,23,24,25,26 },
		{ 27,28,29,30,31,32,33,34,35 },
		{ 36,37,38,39,40,41,42,43,44 },
		{ 45,46,47,48,49,50,51,52,53 },
		{ 54,55,56,57,58,59,60,61,62 },
		{ 63,64,65,66,67,68,69,70,71 },
		{ 72,73,74,75,76,77,78,79,80 }
	},
	{
		{  3, 4, 5, 6, 7, 8, 0, 1, 2 },
		{ 12,13,14,15,16,17, 9,10,11 },
		{ 21,22,23,24,25,26,18,19,20 },
		{ 30,31,32,33,34,35,27,28,29 },
		{ 39,40,41,42,43,44,36,37,38 },
		{ 48,49,50,51,52,53,45,46,47 },
		{ 57,58,59,60,61,62,54,55,56 },
		{ 66,67,68,69,70,71,63,64,65 },
		{ 75,76,77,78,79,80,72,73,74 }
	},
	{
		{  6, 7, 8, 0, 1, 2, 3, 4, 5 },
		{ 15,16,17, 9,10,11,12,13,14 },
		{ 24,25,26,18,19,20,21,22,23 },
		{ 33,34,35,27,28,29,30,31,32 },
		{ 42,43,44,36,37,38,39,40,41 },
		{ 51,52,53,45,46,47,48,49,50 },
		{ 60,61,62,54,55,56,57,58,59 },
		{ 69,70,71,63,64,65,66,67,68 },
		{ 78,79,80,72,73,74,75,76,77 }
	},
	{
		{ 27,28,29,30,31,32,33,34,35 },
		{ 36,37,38,39,40,41,42,43,44 },
		{ 45,46,47,48,49,50,51,52,53 },
		{ 54,55,56,57,58,59,60,61,62 },
		{ 63,64,65,66,67,68,69,70,71 },
		{ 72,73,74,75,76,77,78,79,80 },
		{  0, 1, 2, 3, 4, 5, 6, 7, 8 },
		{  9,10,11,12,13,14,15,16,17 },
		{ 18,19,20,21,22,23,24,25,26 }
	},
	{
		{ 30,31,32,33,34,35,27,28,29 },
		{ 39,40,41,42,43,44,36,37,38 },
		{ 48,49,50,51,52,53,45,46,47 },
		{ 57,58,59,60,61,62,54,55,56 },
		{ 66,67,68,69,70,71,63,64,65 },
		{ 75,76,77,78,79,80,72,73,74 },
		{  3, 4, 5, 6, 7, 8, 0, 1, 2 },
		{ 12,13,14,15,16,17, 9,10,11 },
		{ 21,22,23,24,25,26,18,19,20 }
	},
	{
		{ 33,34,35,27,28,29,30,31,32 },
		{ 42,43,44,36,37,38,39,40,41 },
		{ 51,52,53,45,46,47,48,49,50 },
		{ 60,61,62,54,55,56,57,58,59 },
		{ 69,70,71,63,64,65,66,67,68 },
		{ 78,79,80,72,73,74,75,76,77 },
		{  6, 7, 8, 0, 1, 2, 3, 4, 5 },
		{ 15,16,17, 9,10,11,12,13,14 },
		{ 24,25,26,18,19,20,21,22,23 }
	},
	{
		{ 54,55,56,57,58,59,60,61,62 },
		{ 63,64,65,66,67,68,69,70,71 },
		{ 72,73,74,75,76,77,78,79,80 },
		{  0, 1, 2, 3, 4, 5, 6, 7, 8 },
		{  9,10,11,12,13,14,15,16,17 },
		{ 18,19,20,21,22,23,24,25,26 },
		{ 27,28,29,30,31,32,33,34,35 },
		{ 36,37,38,39,40,41,42,43,44 },
		{ 45,46,47,48,49,50,51,52,53 }
	},
	{
		{ 57,58,59,60,61,62,54,55,56 },
		{ 66,67,68,69,70,71,63,64,65 },
		{ 75,76,77,78,79,80,72,73,74 },
		{  3, 4, 5, 6, 7, 8, 0, 1, 2 },
		{ 12,13,14,15,16,17, 9,10,11 },
		{ 21,22,23,24,25,26,18,19,20 },
		{ 30,31,32,33,34,35,27,28,29 },
		{ 39,40,41,42,43,44,36,37,38 },
		{ 48,49,50,51,52,53,45,46,47 }
	},
	{
		{ 60,61,62,54,55,56,57,58,59 },
		{ 69,70,71,63,64,65,66,67,68 },
		{ 78,79,80,72,73,74,75,76,77 },
		{  6, 7, 8, 0, 1, 2, 3, 4, 5 },
		{ 15,16,17, 9,10,11,12,13,14 },
		{ 24,25,26,18,19,20,21,22,23 },
		{ 33,34,35,27,28,29,30,31,32 },
		{ 42,43,44,36,37,38,39,40,41 },
		{ 51,52,53,45,46,47,48,49,50 }
	},
	{
		{  0, 9,18,27,36,45,54,63,72 },
		{  1,10,19,28,37,46,55,64,73 },
		{  2,11,20,29,38,47,56,65,74 },
		{  3,12,21,30,39,48,57,66,75 },
		{  4,13,22,31,40,49,58,67,76 },
		{  5,14,23,32,41,50,59,68,77 },
		{  6,15,24,33,42,51,60,69,78 },
		{  7,16,25,34,43,52,61,70,79 },
		{  8,17,26,35,44,53,62,71,80 }
	},
	{
		{ 27,36,45,54,63,72, 0, 9,18 },
		{ 28,37,46,55,64,73, 1,10,19 },
		{ 29,38,47,56,65,74, 2,11,20 },
		{ 30,39,48,57,66,75, 3,12,21 },
		{ 31,40,49,58,67,76, 4,13,22 },
		{ 32,41,50,59,68,77, 5,14,23 },
		{ 33,42,51,60,69,78, 6,15,24 },
		{ 34,43,52,61,70,79, 7,16,25 },
		{ 35,44,53,62,71,80, 8,17,26 }
	},
	{
		{ 54,63,72, 0, 9,18,27,36,45 },
		{ 55,64,73, 1,10,19,28,37,46 },
		{ 56,65,74, 2,11,20,29,38,47 },
		{ 57,66,75, 3,12,21,30,39,48 },
		{ 58,67,76, 4,13,22,31,40,49 },
		{ 59,68,77, 5,14,23,32,41,50 },
		{ 60,69,78, 6,15,24,33,42,51 },
		{ 61,70,79, 7,16,25,34,43,52 },
		{ 62,71,80, 8,17,26,35,44,53 }
	},
	{
		{  3,12,21,30,39,48,57,66,75 },
		{  4,13,22,31,40,49,58,67,76 },
		{  5,14,23,32,41,50,59,68,77 },
		{  6,15,24,33,42,51,60,69,78 },
		{  7,16,25,34,43,52,61,70,79 },
		{  8,17,26,35,44,53,62,71,80 },
		{  0, 9,18,27,36,45,54,63,72 },
		{  1,10,19,28,37,46,55,64,73 },
		{  2,11,20,29,38,47,56,65,74 }
	},
	{
		{ 30,39,48,57,66,75, 3,12,21 },
		{ 31,40,49,58,67,76, 4,13,22 },
		{ 32,41,50,59,68,77, 5,14,23 },
		{ 33,42,51,60,69,78, 6,15,24 },
		{ 34,43,52,61,70,79, 7,16,25 },
		{ 35,44,53,62,71,80, 8,17,26 },
		{ 27,36,45,54,63,72, 0, 9,18 },
		{ 28,37,46,55,64,73, 1,10,19 },
		{ 29,38,47,56,65,74, 2,11,20 }
	},
	{
		{ 57,66,75, 3,12,21,30,39,48 },
		{ 58,67,76, 4,13,22,31,40,49 },
		{ 59,68,77, 5,14,23,32,41,50 },
		{ 60,69,78, 6,15,24,33,42,51 },
		{ 61,70,79, 7,16,25,34,43,52 },
		{ 62,71,80, 8,17,26,35,44,53 },
		{ 54,63,72, 0, 9,18,27,36,45 },
		{ 55,64,73, 1,10,19,28,37,46 },
		{ 56,65,74, 2,11,20,29,38,47 }
	},
	{
		{  6,15,24,33,42,51,60,69,78 },
		{  7,16,25,34,43,52,61,70,79 },
		{  8,17,26,35,44,53,62,71,80 },
		{  0, 9,18,27,36,45,54,63,72 },
		{  1,10,19,28,37,46,55,64,73 },
		{  2,11,20,29,38,47,56,65,74 },
		{  3,12,21,30,39,48,57,66,75 },
		{  4,13,22,31,40,49,58,67,76 },
		{  5,14,23,32,41,50,59,68,77 }
	},
	{
		{ 33,42,51,60,69,78, 6,15,24 },
		{ 34,43,52,61,70,79, 7,16,25 },
		{ 35,44,53,62,71,80, 8,17,26 },
		{ 27,36,45,54,63,72, 0, 9,18 },
		{ 28,37,46,55,64,73, 1,10,19 },
		{ 29,38,47,56,65,74, 2,11,20 },
		{ 30,39,48,57,66,75, 3,12,21 },
		{ 31,40,49,58,67,76, 4,13,22 },
		{ 32,41,50,59,68,77, 5,14,23 }
	},
	{
		{ 60,69,78, 6,15,24,33,42,51 },
		{ 61,70,79, 7,16,25,34,43,52 },
		{ 62,71,80, 8,17,26,35,44,53 },
		{ 54,63,72, 0, 9,18,27,36,45 },
		{ 55,64,73, 1,10,19,28,37,46 },
		{ 56,65,74, 2,11,20,29,38,47 },
		{ 57,66,75, 3,12,21,30,39,48 },
		{ 58,67,76, 4,13,22,31,40,49 },
		{ 59,68,77, 5,14,23,32,41,50 }
	}};
 
byte	tperm[6][3]=	{  
	{ 0, 1, 2 },{ 0, 2, 1 },{ 1, 0, 2 },
	{ 1, 2, 0 },{ 2, 0, 1 },{ 2, 1, 0 }	};

byte	tpart[9][5]=	{ 
	{ 0, 0, 0, 0, 0 },{ 0, 0, 0, 0, 0 },{ 0, 0, 0, 0, 0 },
	{ 4, 5, 6, 7, 8 },{ 3, 5, 6, 7, 8 },{ 3, 4, 6, 7, 8 },
	{ 7, 8, 3, 4, 5 },{ 6, 8, 3, 4, 5 },{ 6, 7, 3, 4, 5 }	};

byte	tboxOffset[9]=	{ 0, 0, 0, 3, 3, 3, 6, 6, 6	};

Canon_t BestInit={
	0,0, // aut box
	{10,10,10,10,10,10,10,10,10,10}, // map
	{0,1,2,3,4,5,6,7,8}, // rows
	{0,1,2,3,4,5,6,7,8}  // cols
};

Canon_t TestInit={
	0,0, // aut box
	{0,0,0,0,0,0,0,0,0,0}, // map
	{0,0,0,0,0,0,0,0,0}, // rows
	{0,0,0,0,0,0,0,0,0}  // cols
};

char * t16[401]={
	"6789123789123456","6789123789123465","6789123789123564","6789123789132465",
	"6789123789132546","6789123789132564","6789123789231564","6789123789231645",
	"6789123798132465","6789123798132546","6789123798132564","6789123798213564",
	"6789123798213654","6789123798231564","6789123798231645","6789123897231564",
	"6789123897231645","6789132789123546","6789132789132546","6789132789132564",
	"6789132789213456","6789132789213645","6789132789213654","6789132789231546",
	"6789132789231564","6789132879231564","6789231789123645","6789231789132546",
	"6789231789231564","6789231789312456","6789231798213645","7189236689237145",
	"7189236689237154","7189236689237415","7189236689237451","7189236689237514",
	"7189236689237541","7189236689273145","7189236689273154","7189236689273415",
	"7189236689273451","7189236689273514","7189236689273541","7189236689327145",
	"7189236689327154","7189236689327415","7189236689327451","7189236689327514",
	"7189236689327541","7189236689372145","7189236689372154","7189236689372415",
	"7189236689372451","7189236689372514","7189236689372541","7189236689723145",
	"7189236689723154","7189236689723415","7189236689723514","7189236689723541",
	"7189236689732145","7189236689732154","7189236689732415","7189236689732514",
	"7189236689732541","7189236698237145","7189236698237154","7189236698237415",
	"7189236698237514","7189236698237541","7189236698273145","7189236698273154",
	"7189236698273415","7189236698273514","7189236698273541","7189236698327145",
	"7189236698327154","7189236698327415","7189236698327541","7189236698372145",
	"7189236698372154","7189236698372415","7189236698372514","7189236698372541",
	"7189236698723145","7189236698723154","7189236698723415","7189236698723514",
	"7189236698732145","7189236698732154","7189236698732415","7189236698732514",
	"7189236869237145","7189236869237514","7189236869273145","7189236869273154",
	"7189236869273415","7189236869273514","7189236869327154","7189236869327415",
	"7189236869327514","7189236869372145","7189236869372154","7189236869372415",
	"7189236869372514","7189236869723145","7189236869723154","7189236869723514",
	"7189236869732145","7189236869732154","7189236896237145","7189236896237154",
	"7189236896237514","7189236896273145","7189236896273154","7189236896273514",
	"7189236896327145","7189236896327154","7189236896327514","7189236896372145",
	"7189236896372154","7189236896372514","7189236896723154","7189236896723514",
	"7189236896732154","7189236896732514","7189236968237154","7189236968237514",
	"7189236968273514","7189236968327154","7189236968327514","7189236968372154",
	"7189236968372514","7189236968723154","7189236968732154","7189236986237154",
	"7189236986273154","7189236986327154","7189236986372154","7189263689237145",
	"7189263689237415","7189263689237451","7189263689237514","7189263689273154",
	"7189263689273415","7189263689273451","7189263689273514","7189263689273541",
	"7189263689327154","7189263689327415","7189263689327514","7189263689327541",
	"7189263689372145","7189263689372154","7189263689372415","7189263689372451",
	"7189263689372514","7189263689723145","7189263689723154","7189263689723451",
	"7189263689732145","7189263689732154","7189263689732415","7189263689732451",
	"7189263689732514","7189263689732541","7189263698237154","7189263698237415",
	"7189263698237451","7189263698237514","7189263698273145","7189263698273415",
	"7189263698273451","7189263698273514","7189263698327145","7189263698327154",
	"7189263698327415","7189263698327451","7189263698327514","7189263698372154",
	"7189263698372415","7189263698372514","7189263698372541","7189263698732145",
	"7189263698732154","7189263698732451","7189263869237154","7189263869237415",
	"7189263869237514","7189263869273451","7189263869327415","7189263869327451",
	"7189263869327514","7189263869372145","7189263869372154","7189263869372514",
	"7189263896237145","7189263896237154","7189263896237451","7189263896327145",
	"7189263896327154","7189263896327415","7189263896327451","7189263896327514",
	"7189263896327541","7189263896372145","7189263896372154","7189263896372451",
	"7189263968327145","7189263968327154","7189263968327415","7189263968327514",
	"7189263968327541","7189263968372145","7189263986327145","7189263986327154",
	"7189263986327451","7189326689237451","7189326689237514","7189326689237541",
	"7189326689273145","7189326689273451","7189326689273541","7189326689327154",
	"7189326689327451","7189326689327541","7189326689372415","7189326689372541",
	"7189326689723145","7189326689723415","7189326689732145","7189326689732415",
	"7189326689732514","7189326689732541","7189326698237145","7189326698237541",
	"7189326698273514","7189326698273541","7189326698732415","7189326869372514",
	"7189623689237145","7189623689237154","7189623689273145","7189623689273154",
	"7189623689273541","7189623689327145","7189623689327154","7189623689372145",
	"7189623689372154","7189623689372514","7189623689723145","7189623689723154",
	"7189623689723415","7189623689723451","7189623689723514","7189623689723541",
	"7189623689732145","7189623689732154","7189623689732415","7189623689732451",
	"7189623689732514","7189623689732541","7189623698237145","7189623698237154",
	"7189623698237541","7189623698273145","7189623698273154","7189623698327145",
	"7189623698327154","7189623698327514","7189623698372145","7189623698372154",
	"7189623698732145","7189623698732154","7189623698732415","7189623698732514",
	"7189623698732541","7189623869237145","7189623869273145","7189623869273154",
	"7189623869273451","7189623869327154","7189623869372145","7189623869372154",
	"7189623896237145","7189623896237154","7189623896237415","7189623896237451",
	"7189623896237514","7189623896237541","7189623896327145","7189623896327154",
	"7189623896327415","7189623896327451","7189623896327514","7189623896372145",
	"7189623896372154","7189623896372451","7189623968327145","7189623968327154",
	"7189623968327415","7189623968372145","7189623968372154","7189623986327145",
	"7189623986327154","7189623986327415","7189623986327451","7189623986327514",
	"7189623986327541","7189632689237145","7189632689273145","7189632689273154",
	"7189632689273514","7189632689327154","7189632689372145","7189632689372154",
	"7189632689723145","7189632689723514","7189632689732145","7189632689732154",
	"7189632689732514","7189632689732541","7189632698237145","7189632698237154",
	"7189632698237514","7189632698273145","7189632698327145","7189632698327154",
	"7189632698327541","7189632698372154","7189632698732145","7189632698732514",
	"7189632869273145","7189632869372145","7189632896237145","7189632896237415",
	"7189632896327145","7189632896327154","7189632896327451","7189632896327541",
	"7189632896372145","7189632896372154","7189632896372451","7189632968327145",
	"7189632968327154","7189632968327451","7189632986327145","7289163689173452",
	"7289163689713254","7289163698137425","7289163698137524","7289163698317254",
	"7289163698317524","7289163698713254","7289163869713245","7289163869731245",
	"7289163869731524","7289163896317245","7289163896731524","7289613689173245",
	"7289613689713245","7289613689713254","7289613698137254","7289613698317245",
	"7289613698317254","7289613698713245","7289613869713245","7289613869731245",
	"7289613869731254","7289613896137245","7289613896137254","7289613896317245",
	"7289613896317425","7289613896731245","7289613896731254","7289613968137245",
	"7289613968137254","7289613968731245","7289613986137245","7289631689173245",
	"7289631689713254","7289631698317254","7289631869713245","7289631869713254",
	"7289631869731245","7289631869731254","7289631896137245","7289631896137254",
	"7289631896137425","7289631896317245","7289631896317254","7289631896731245",
	"7289631968137254","7289631968731245","7289631986137245","7389612896127354",
	"7389612896172354","7389612896271354","7389612896721354","7389621896217354",
	"7893612986217354" 
};

// table used to compress expand in digit mode 50 cells

byte tcompact[46]={
	11,12,13,14,15,16,			// row 2 6 values
	18,19,21,22,24,25,			// row 3 6 values 2 per box
	27,28,29,30,31,32,33,34,	// row 4 8 values
	36,37,38,39,40,41,42,43,    // row 5 8 values
	45,46,48,49,51,52,			// row 6 6 balues 2 per box
	54,55,56,57,58,59,			// row 7 6 values box 9 known
	63,64,65,66,67,68			// row 8 6 values box 9 known
};

char * puzstart=
	"12345678945................2.....................................................";